package com.chapter7;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class StringManipulations {

	public List<String> anagrams(String[] strs) {
		List<String> l = new ArrayList<String>();
		Map<BigInteger,List<String>> mapper=new HashMap<BigInteger,List<String>>();
		int[] primes={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
		for(String s:strs){
			BigInteger bg=new BigInteger("1");
			for(int i=0;i<s.length();i++){
				int val=s.charAt(i)-'a';
				val=primes[val];
				bg=bg.multiply(BigInteger.valueOf(val));
			}
			if(mapper.containsKey(bg)){
				mapper.get(bg).add(s);
			}
			else{
				List<String> li=new ArrayList<String>();
				li.add(s);
				mapper.put(bg, li);
			}
		}

		for (Entry<BigInteger, List<String>> entry : mapper.entrySet())
		{
			if(entry.getValue().size()>1)
				l.addAll(entry.getValue());
		}
		return l;
	}
	public double getPower(double x, int y){
		if(y==0)
			return 1;
		else if(y==1)
			return x;
		else if(y%2==0){
			double value=getPower(x,y/2);
			return value*value;
		}
		else{
			double value=getPower(x,(y-1)/2);
			return value*value*x;
		}
	}
	public long stringtoInt(String s){
		long num=0;
		boolean isNegative=false;
		if(s.charAt(0)=='-')
		{
			isNegative=true;
			s=s.substring(1, s.length());
		}
		for (int i = 0; i < s.length(); i++) {
			int val=s.charAt(i)-'0';
			if(val<0 || val>9){
				return Long.MAX_VALUE;
			}
			num=num + val*(long)getPower(10,s.length()-1-i);
		}
		if(isNegative)
			num=-num;
		return num;
	}

	public String inttostring(long num){
		String s="";
		boolean isNegative=false;
		if(num<0)
		{
			isNegative=true;
			num=-num;
		}
		long temp=num;
		int count=0;
		while(temp>0){
			temp=temp/10;
			count++;
		}
		for (int i = 0; i < count; i++) {
			long val=num%10;
			s=val+s;
			num=num/10;
		}
		if(isNegative)
			s='-'+s;
		return s;
	}

	public String replaceString(String input, String s1, String s2){
		if(s1.length()==0 || s2.length()==0)
			return input;
		List<Integer> index=getOccurenceIndex(input, s1);
		String output="";
		int beginIndex=0;
		for(int i=0;i<index.size();i++){
			int ind=index.get(i);
			output=output+input.substring(beginIndex, ind);
			output=output+s2;
			beginIndex=ind+s1.length();
		}
		output=output+input.substring(beginIndex, input.length());
		return output;
	}

	public String replaceString2(String input, String s1, String s2){
		if(s1.length()==0 || s2.length()==0)
			return input;
		List<Integer> index=getOccurenceIndex(input, s1);
		int indexOutput=0;
		int indexInput=0;
		char[] output=new char[input.length()-index.size()*s1.length()+index.size()*s2.length()];
		for(int i=0;i<index.size();i++){
			int ind=index.get(i);
			while(indexInput<ind){
				output[indexOutput++]=input.charAt(indexInput++);
			}
			int j=0;
			while(indexInput<ind+s2.length())
			{
				output[indexOutput++]=s2.charAt(j++);
				indexInput++;
			}
			indexInput=ind+s1.length();
		}
		String remaining=input.substring(indexInput, input.length());
		for(int i=0;i<remaining.length();i++){
			output[indexOutput++]=remaining.charAt(i);
		}
		return new String(output);
	}

	public List<Integer> getOccurenceIndex(String input, String s1){
		List<Integer> index=new ArrayList<Integer>();
		for(int i=0;i<input.length()-s1.length();i++){
			int j=0;
			while(j<s1.length() && input.charAt(i+j)==s1.charAt(j)){
				j++;
			}
			if(j==s1.length())
			{
				index.add(i);
				i=i+j-1;
			}

		}
		return index;
	}

	public boolean isPalindrome(String input){
		int i=0;
		int j=input.length()-1;
		while(i<j){
			int beginVal=input.charAt(i)-'a';
			if(beginVal<0 || beginVal>26)
			{
				i++;
				continue;
			}
			int endVal=input.charAt(j)-'a';
			if(endVal<0 || endVal>26)
			{
				j--;
				continue;
			}
			if(beginVal==endVal){
				i++;
				j--;
			}
			else
				return false;
		}
		return true;
	}

	public String reverseWords(String input){
		int i;
		for(i=0;i<input.length();i++)
			if(input.charAt(i)==' ')
				break;
		if(i==input.length())
			return input;
		return reverseWords(input.substring(i+1, input.length()))+" "+input.substring(0,i);
	}

	public void ReverseAllWords(char[] in_text)
	{
		int lindex = 0;
		int rindex = in_text.length- 1;
		if (rindex > 1)
		{
			//reverse complete phrase
			ReverseString(in_text, 0, rindex);

			//reverse each word in resultant reversed phrase
			for (rindex = 0; rindex <= in_text.length; rindex++)
			{
				if (rindex == in_text.length || in_text[rindex] == ' ')
				{
					ReverseString(in_text, lindex, rindex - 1);
					lindex = rindex + 1;
				}
			}
		}
		System.out.println(in_text);
	}

	public void ReverseString(char[] intext, int lindex, int rindex)
	{
		char tempc;
		while (lindex < rindex)
		{
			tempc = intext[lindex];
			intext[lindex++] = intext[rindex];
			intext[rindex--] = tempc;
		}
	}

	public void getMnemonics(String number){
		String[] A={"0","1","abc","def","ghi","jkl","mno","pqrs","yuv","wxyz"};
		char[] output=new char[number.length()];
		getMnemonicsHelper2(number, A,0, output);
	}

	public void getMnemonicsHelper(String number, String[] A, int index, char[] output){
		if(index==number.length()){
			System.out.println(output);
			return;
		}
		int val=number.charAt(index)-'0';
		for(int i=0;i<A[val].length();i++){
			output[index]=A[val].charAt(i);
			getMnemonicsHelper(number, A, index+1,output);
		}

	}
	//TO DO

	public void getMnemonicsHelper2(String number, String[] A, int index, char[] output){
		for(int i=0;i<number.length();i++){
			int val=number.charAt(i)-'0';
			for(int j=0;j<A[val].length();j++){
				output[i]=A[val].charAt(j);
				if(i==number.length()-1)
					System.out.println(output);
			}	
		}
	}

	public void lookAndSay(int n){
		String start="1";
		getNextNumber(start,n);
	}

	public void getNextNumber(String curr, int n){
		if(n==1)
			return;
		String op="";
		for(int i=0;i<curr.length();i++){
			int count=1;
			int j=0;
			while(i+j+1<curr.length() && curr.charAt(i+j)==curr.charAt(i+1+j++))
				count++;
			op=op+count+curr.charAt(i);
			i=i+count-1;
		}
		System.out.println(op);
		getNextNumber(op,n-1);
	}

	public long romanToDecimal(String roman){
		long op=0;
		int i=0;
		int val;
		Map<Character,Integer> mapper=new HashMap<Character, Integer>();
		//initialization
		mapper.put('I', 1);
		mapper.put('V', 5);
		mapper.put('X', 10);
		mapper.put('L', 50);
		mapper.put('C', 100);
		mapper.put('D', 500);
		mapper.put('M', 1000);
		while(i<roman.length()){
			if((roman.charAt(i)=='I' && (roman.charAt(i+1)=='V'||roman.charAt(i+1)=='X'))
					||(roman.charAt(i)=='X' && (roman.charAt(i+1)=='L'||roman.charAt(i+1)=='C'))
					|| (roman.charAt(i)=='C' && (roman.charAt(i+1)=='D'||roman.charAt(i+1)=='M')))
			{
				val=mapper.get(roman.charAt(i+1))-1;
				i=i+2;
				op=op+val;
			}
			else{
				val=mapper.get(roman.charAt(i++));
				op=op+val;
			}
		}
		return op;
	}
	public String getSnakeString(String s){
		String top="";
		String mid="";
		String bottom="";
		for(int i=0;i<s.length();i++){
			if(i%4==1){
				top=top+s.charAt(i);
			}
			else
				top=top+" ";
			if(i%4==3)
				bottom=bottom+s.charAt(i);
			else
				bottom=bottom+" ";
			if(i%2==0)
				mid=mid+s.charAt(i);
			else
				mid=mid+" ";
		}
		System.out.println(top);
		System.out.println(mid);
		System.out.println(bottom);
		String st=top+mid+bottom;
		return st.replaceAll("\\s+","");
	}

	public String gammaEncode(int[] A){
		String s="";
		for(int i=0;i<A.length;i++){
			String p=getBinaryfromDecimal(A[i]);
			int siz=p.length();
			for(int j=0;j<siz-1;j++)
				p="0"+p;
			s=s+p;
		}
		List<Integer> arr=gammaDecode(s);
		return s;
	}
	public String getBinaryfromDecimal(int n){
		String b="";
		while(n!=0){
			b=(n & 1)+b;
			n=n>>1;
		}
		return b;
	}

	public int getDecimalfromBinary(String b){
		int number=0;
		for(int i=0;i<b.length();i++){
			int val=b.charAt(i)-'0';
			number=number+(int)getPower(2, b.length()-1-i)*val;
		}
		return number;
	}

	public List<Integer> gammaDecode(String s){
		List<Integer> l=new ArrayList<Integer>();
		int i=0,count=0;
		while(i<s.length()){
			if(s.charAt(i)=='0'){
				count++;
				i++;
			}
			else{
				l.add(getDecimalfromBinary(s.substring(i, i+count+1)));
				i=i+count+1;
				count=0;
			}
		}
		return l;
	}

	public boolean patternMatch(int[] A, String input, String pattern){
		int i,j;
		int[] B=new int[A.length+2];
		for(i=1;i<=A.length;i++)
			B[i]=A[i-1];
		B[0]=0;
		B[B.length-1]=input.length();
		for(i=0;i<pattern.length();i++){
			char c=pattern.charAt(i);
			for(j=i+1;j<pattern.length();j++){
				if(pattern.charAt(j)==c){
					if(!input.substring(B[i], B[i+1]).equals(input.substring(B[j], B[j+1])))
						return false;
				}
			}
		}
		return  true;
	}

	public boolean matchPatterns(String input, String pattern){
		int[] A=new int[pattern.length()-1];
		return matchPatterns(A,0,0,input,pattern);
	}
	public boolean matchPatterns(int[] A, int index, int l, String input, String pattern){
		if(l==A.length){
			if(patternMatch(A,input,pattern))
				return true;
			return false;
		}
		for(int i=index;i<input.length()-A.length+l+1;i++){
			A[l]=i;
			boolean value= matchPatterns(A,i+1,l+1,input,pattern);
			if(value)
				return true;
		}
		return false;
	}

	public boolean isMatch(String input, String pattern, int inpInd, int pInd){
		if(pInd==pattern.length() && inpInd==input.length())
			return true;
		if(pInd>=pattern.length() || inpInd>=input.length())
			return false;
		if(pInd+1==pattern.length() || pattern.charAt(pInd+1)!='*'){
			if((pattern.charAt(pInd)=='.' && inpInd<input.length())|| pattern.charAt(pInd)==input.charAt(inpInd))
				return isMatch(input,pattern,inpInd+1,pInd+1);
			return false;
		}
		else{
			int i=0;
			while((pattern.charAt(pInd)=='.' && inpInd<input.length())|| pattern.charAt(pInd)==input.charAt(inpInd)){
				if(isMatch(input,pattern,inpInd+i,pInd+2))
					return true;
				i++;
			}
		}
		return isMatch(input,pattern,inpInd,pInd+2);
	}
}
